package com.yww.algorithm.recursion.fibonacci;

import java.util.Arrays;

/**
 * @author yww
 * @description 斐波那契 递归
 * @since 2024/1/31 14:44
 */
public final class Fibonacci {

    public static int fibonacci(int n) {
        int[] cache = new int[n + 1];
        Arrays.fill(cache, -1);
        cache[0] = 0;
        cache[1] = 1;
        return f02(n, cache);
    }

    // 缓存优化递归，避免重复递归
    private static int f02(int n, int[] cache) {
        if (cache[n] != -1) {
            return cache[n];
        }
        cache[n] = f02(n - 1, cache) + f02(n - 2, cache);
        return cache[n];
    }

    private static int f01(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        return f01(n - 1) + f01(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(f01(5));
        System.out.println(f01(7));

        System.out.println(fibonacci(5));
        System.out.println(fibonacci(7));
    }
}
